20. 有效的括号
20. 有效的括号
分析
由于栈结构的特殊性，非常适合做对称匹配类的题目。即必须按照出现的顺序反向出现另一半的这种题目
括号匹配就是一个典型的题目，实际上编译器词法分析的过程中就是用栈来判断多层嵌套的括号是否完整的。除此之外，Linux 系统中，cd 这个进入目录的命令我们应该再熟悉不过了。
cd a/b/c/../../
这个命令最后进入 a 目录，系统是如何知道进入了 a 目录呢 ，这也是栈的应用（其实可以出一道相应的面试题了）（还真有 71. 简化路径）
说回本题的解题思路：
我最开始想到用三个栈，每一个栈处理一种括号，但是这样的话， ([)] 的结果就会是 true，但是我们知道这样是不对的。所以最总还是只能用一个栈来处理。
然后实际的处理逻辑是，遍历字符串的所有字符
- 碰到左括号，直接入栈，
- 碰到右括号，看栈顶是不是与之对应的左括号，是则将栈顶出栈，否则直接返回 false，注意栈顶可能为 null
- 遍历完所有元素之后，查看栈的长度，如果长度为 0，则返回 true，否则返回 false
这么做法是没问题的，不过还有一个更方便简洁的做法，就是遍历字符的时候
- 碰到左括号，把与之对应的右括号入库
- 碰到右括号，直接对比栈顶是不是与之相同的字符，是则将栈顶出栈，否则直接返回 false，注意栈顶可能为 null
- 遍历完所有元素之后，查看栈的长度，如果长度为 0，则返回 true，否则返回 false
其实无论是什么做法，都免不了从左括号到右括号，或者右括号到左括号的映射。第一种方法是将这个映射的判断留在了出栈的时候，而第二种写法是将这个映射留在了入栈的时候，其实两种方法差别不大。
这时，我们也能总结出栈这个数据结构的最佳使用姿势：如果待入栈的元素跟栈顶的元素相同，则弹出栈顶元素，同时处理下一个待入栈的元素。
因此，如果我们遇到需要我们以与遍历顺序相反的顺序倒叙检查的题目，那用栈来保存遍历过的元素就是最合适的。用栈解决问题的时候，我们要注意，其实我们总共有两种遍历顺序，一种遍历顺序是我们从头向后遍历数组或者列表的顺序，一种是将元素放入栈中，然后倒序拿出来的顺序，这两种顺序的配合是我们思考问题的关键。
解题
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if ('(' == chars[i]) {
stack.push(')');
}else if ('[' == chars[i]) {
stack.push(']');
}else if ('{' == chars[i]) {
stack.push('}');
}else{
// 栈顶可能为空
if(stack.peek() == null){
return false;
}else if(stack.peek() != chars[i]){
return false;
}else{
stack.pop();
}
}
}
return stack.size() == 0 ;
}